\section{Introduction}
\label{s:intro}

We consider \emph{$K$-Facility Location games}, where $K$ facilities are placed on the real line based on the preferences of strategic agents. Such problems are motivated by natural scenarios in Social Choice, where the government plans to build a fixed number of public facilities, such as libraries, post offices, information kiosks, etc., in an area (see e.g. \cite{Miy01}). The choice of the locations is based on the preferences of local people, or \emph{agents}. So each agent reports her ideal location, and the government applies a \emph{mechanism} mapping the agents' preferences to $K$ facility locations.
%
The government's objective is to minimize the \emph{social cost}, namely the total distance of the agents' locations to the nearest facility. On the other hand, the agents seek to minimize their \emph{individual cost}, namely the distance of their location to the nearest facility. In fact, an agent may even misreport her ideal location in an attempt of manipulating the mechanism. Therefore, the mechanism should be \emph{strategyproof}, i.e., should ensure that no agent can benefit from misreporting her location, or even \emph{group strategyproof}, i.e., should ensure that for any group of agents misreporting their locations, at least one of them does not benefit. Moreover, to compute a socially desirable outcome, the mechanism should achieve a reasonable approximation to the optimal social cost.


\smallskip\noindent{\bf Previous Work.}
%
In addition to strategyproofness, which is an essential property of any mechanism, Social Choice suggests a few additional efficiency-related properties, e.g., the onto condition, the non-dictatorship condition, and Pareto-efficiency, that usually accompany strategyproofness, and ensure that the mechanism's outcome is socially desirable (or at least tolerable). There are several examples of beautiful characterization theorems which state that for a particular domain, the class of strategyproof mechanisms with some efficiency-related properties coincides with a rather restricted class of mechanisms (see e.g., \cite{Bar01}). %Prominent among them is the impossibility result of %Gibbard-Satterthwaite
%\cite{Gibb73,Satter75}, which states that for general preference domains, if there are at least three possible outcomes, any onto strategyproof mechanism is a dictatorship.
%
A notable example of a problem admitting a rich class of strategyproof mechanisms is that of locating a single facility on the real line, where the agents' preferences are single-peaked. The classical characterization of \cite{Moul80} shows that the class of strategyproof mechanisms for 1-Facility Location on the line coincides with the class of generalized median voter schemes. In fact, \cite{SV02} proved that the characterization extends to tree metrics, while for non-tree metrics, any onto strategyproof mechanism is a dictatorship.


%where the class of strategyproof mechanisms coincides with the class of extended median voter schemes \cite{SV02}. On the negative side, \cite{SV02} proved that for non-tree metrics, any onto strategyproof mechanism is a dictatorship.

Adopting an algorithmic viewpoint, %of Social Choice,
\cite{PT09} introduced the framework of \emph{approximate mechanism design without money}. The idea is to consider game-theoretic versions of optimization problems,
%
%where the mechanism must be strategyproof, without resorting to monetary transfers,
%
where a social cost function summarizes (or even strengthens) the efficiency-related properties. Now, any reasonable approximation to the optimal solution can be regarded as a socially desirable outcome, and we seek to determine the best approximation ratio achievable by strategyproof mechanisms.
%
For example, \cite{PT09} observed that extended median voter schemes include the {\sc Median} mechanism, that places a single facility so that the total distance to the agents is minimized, and thus, 1-Facility Location in tree metrics can be solved optimally by a strategyproof mechanism.
%
On the other hand, the negative result of \cite{SV02} implies that the best approximation ratio achievable by deterministic strategyproof mechanisms for 1-Facility Location in general metrics is $n-1$, where $n$ is the number of agents.

\cite{PT09} considered several location problems on the real line, and obtained upper and lower bounds on the approximation ratio achievable by strategyproof mechanisms. For 2-Facility Location, they suggested the {\sc Two-Extremes} mechanism, that places the facilities at the leftmost and the rightmost locations, and achieves an approximation ratio of $n-2$. On the negative side, they proved a lower bound of $3/2$ on the approximation ratio of any deterministic mechanism, and conjectured that the lower bound for deterministic mechanisms is $\Omega(n)$.
%
Subsequently, \cite{LWZ09} strengthened the lower bound for deterministic mechanisms to 2, established a lower bound of 1.045 for randomized mechanisms, and presented a simple randomized $n/2$-approximation mechanism.
%
\cite{LSWZ10} improved the lower bound for deterministic mechanisms to $(n-1)/2$. On the positive side, they presented a deterministic $(n-1)$-approximation mechanism for 2-Facility Location on the circle, and proved that a natural randomized mechanism, the {\sc Proportional} one, is strategyproof and achieves an approximation ratio of 4 for 2-Facility Location in any metric space. \cite{LSWZ10} observed that although {\sc Proportional} is not strategyproof for more than two facilities, its combination with {\sc Two-Extremes} results in a randomized $(n-1)$-approximation mechanism for 3-Facility Location on the line.


\smallskip\noindent{\bf Motivation and Contribution.}
%
Facility Location games are among the central problems in the research agenda of mechanism design without money, and have received considerable attention. Our work is motivated by the apparent difficulty of obtaining any strong(er) positive results on the approximability of $K$-Facility Location by deterministic strategyproof mechanisms.
%
In particular, among the main open problems of \cite{LSWZ10} were to determine the best approximation ratio achievable by deterministic mechanisms for 2-Facility Location on the line, and thus to settle the ``most enigmatic open problem'' of \cite{PT09}, and to investigate the existence of a deterministic mechanism with a bounded approximation ratio for $K$-Facility Location with $K \geq 3$. In this work, we completely resolve the former question, and obtain a strong negative result for the latter.

Attacking these questions requires a complete understanding of the behavior of deterministic strategyproof mechanisms for $K$-Facility Location, similar to that offered by characterization theorems in Social Choice. Hence, we suggest an approach in the intersection of Social Choice and mechanism design without money. More specifically, following the approach of mechanism design without money, we focus on what we call \emph{nice mechanisms}, namely deterministic strategyproof mechanisms with an approximation ratio bounded by some function of $n$ and $K$, and following the approach of Social Choice, we embark on a characterization of nice mechanisms, instead of seeking stronger lower bounds based on carefully selected instances, as e.g. in \cite{PT09,LWZ09,LSWZ10}.
%
In fact, focusing on nice mechanisms greatly facilitates the characterization step, since it excludes several socially intolerable strategyproof mechanisms, such as mechanisms with two dictators.
%
Nevertheless, any characterization of nice mechanisms, even for two facilities, remains an intriguing task, because the preferences are not single-peaked anymore, there is no apparent notion of monotonicity (as e.g., in \cite{Kouts11}), and the combinatorial structure of the problem is significantly more complicated than that for a single facility.

Our main result is an elegant characterization of nice mechanisms for 2-Facility Location on the line. In particular, we show that any nice mechanism for $n \geq 5$ agents either admits a unique dictator, or always places the facilities at the two extremes (Theorem~\ref{thm:2fac-gen}).
%Interestingly, we are aware of only two nice mechanisms for 2-Facility Location on the line: {\sc Two-Extremes}, and {\sc Dictatorial}, an adaptation of the mechanism of \cite{LSWZ10} for the circle.
%
A consequence is that the best approximation ratio achievable by deterministic strategyproof mechanisms is $n-2$. Another rather surprising consequence is that {\sc Two-Extremes} is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for 2-Facility Location on the line.

At the conceptual level, the proof of Theorem~\ref{thm:2fac-gen} proceeds by establishing the characterization at three different levels of generality: 3-agent, 3-location, and general instances. Along the way, we are developing stronger and stronger technical tools that fully describe the behavior of nice mechanisms.
%
To exploit locality, we first focus on well-separated instances with 3 agents, where an isolated agent is served by one facility, and two nearby agents are served by the other facility. Interestingly, we identify two large classes of well-separated instances where any nice mechanism should keep allocating the latter facility to the same agent (Propositions~\ref{prop:right_cover}~and~\ref{prop:left_cover}).
%
Building on this, we show that the location of the facility serving the nearby agents is determined by a generalized median voter scheme, as in \cite{Moul80}, but with a threshold depending on the location and the identity of the isolated agent, and then extend this property to general instances with 3 agents (see Fig.~\ref{fig:allocation}). A key step is to show that the threshold of each isolated agent can only take two extreme values: one corresponding to the existence of a partial dictator, and one corresponding to allocating the facility to the furthest agent (Lemma~\ref{l:i-cases}). Then, considering all possible cases for the agents' thresholds, we show that any nice mechanism for 3 agents either places the facilities at the two extremes, or admits a partial dictator, namely an agent allocated a facility for all, but possibly one, of agent permutations (Theorem~\ref{thm:3agents}).

The next step is that we employ the notion of partial group strategyproofness \cite[Section~3]{LSWZ10} and a new technical tool for moving agents between different coalitions, without affecting the mechanism's outcome (Lemma~\ref{l:any-partition}), and show that any nice mechanism applied to 3-location instances with $n \geq 5$ agents either admits a (full) dictator, or places the facilities at the two extremes (Theorem~\ref{thm:3locations}). Rather surprisingly, this implies that nice mechanisms for 3 agents are somewhat less restricted than nice mechanisms for $n \geq 5$ agents. Finally, in Section~\ref{s:2fac-gen}, we employ induction on the number of different locations, and conclude the proof of Theorem~\ref{thm:2fac-gen}.

In addition to extending the ideas of \cite{Moul80} to 2-Facility Location games and to exploiting the notions of image sets and partial group strategyproofness, in the proof of Theorem~\ref{thm:2fac-gen}, we introduce a few new ideas and technical tools, which provide new insights into the behavior of nice mechanisms for multiple Facility Location games, and may be of independent interest. Among them, we may single out the notion of well-separated instances and the idea of reducing $K$-Facility Location in well-separated instances to a single facility game between the two nearby agents, the ideas used to extend the allocation rule from well-separated instances to general instances, the use of thresholds to eliminate non-nice mechanisms, and the technical tool of moving agents between different coalitions, without affecting the outcome.

For games with more than two facilities, we show that there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio (Theorem~\ref{thm:3facilities}). In fact, for every $K \geq 3$, the proof considers only well-separated instances with $K+1$ agents, and makes use of the technical tools for well-separated instances developed in the proof of Theorem~\ref{thm:2fac-gen}, thus indicating  the generality and the potential applicability of our techniques. At the conceptual level, the proof approach of Theorem~\ref{thm:2fac-gen} and the proof of Theorem~\ref{thm:3facilities} imply that instances with $K+1$ agents are among the hardest ones for deterministic  $K$-Facility Location mechanisms.


\smallskip\noindent{\bf Other Related Work.}
%
In Social Choice, the work on multiple facility location games mostly focuses on Pareto-efficient strategyproof mechanisms that satisfy replacement-domination \cite{Miy01}, and on Pareto-efficient mechanisms whose outcome is consistent with the decisions of the agents served by the same facility \cite{BB06,Ju08}. However, these conditions do not have any immediate implications for the approximability of the social cost, and thus, we cannot technically exploit these results.

\smallskip\noindent{\em Locating a Single Facility.}
%
\cite{AFPT09} gave an almost complete characterization of the approximation ratios achievable by randomized and deterministic strategyproof mechanisms for 1-Facility Location in general metric spaces and rings.
%
Subsequently, \cite{FW11} proved that if we seek to minimize the sum of squares of distances to the agents, the best approximation ratio achievable by strategyproof mechanisms is 1.5 for randomized and 2 for deterministic mechanisms. Moreover, \cite{FW11} presented a class of randomized strategyproof mechanisms that includes all known mechanisms for locating a single facility on the line.


\smallskip\noindent{\em Locating Multiple Facilities.}
%
For $K \geq 4$, the case of $K+1$ agents is the only case where a (randomized) strategyproof mechanism with a bounded approximation ratio is known. \cite{EGTPS11} proved that in this case, the {\sc Inversely Proportional} mechanism is strategyproof and achieves an approximation ratio of $(K+1)/2$ for $K$-Facility Location in general metric spaces. Interestingly, Theorem~\ref{thm:3facilities} shows that these instances are among the hardest ones for deterministic anonymous mechanisms.



\smallskip\noindent{\em Imposing Mechanisms.}
%
\cite{NST10} introduced the notion of \emph{imposing mechanisms}, where the mechanism can restrict how agents exploit its outcome, and thus increase their individual cost if they lie (e.g., for Facility Location games, an imposing mechanism can forbid an agent to connect to some of its facilities).
%
\cite{NST10} combined the almost-strategyproof differentially private mechanism of \cite{MT07} with an imposing mechanism that penalizes lying agents, and obtained a general randomized imposing strategyproof mechanism. As a by-product, they obtained a randomized imposing strategyproof mechanism for $K$-Facility Location that approximates the average optimal social cost within an additive term of roughly $1/n^{1/3}$.
%
Subsequently, \cite{FT10} proved that the imposing version of the {\sc Proportional} mechanism is strategyproof for $K$-Facility Location in general metric spaces, and achieves an approximation ratio of at most $4K$.


